package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

/*
654.最大二叉树
 */
public class Of20210323LeetCode654 {
    public static void main(String[] args) {
        System.out.println(constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0,5}));
    }

    private static TreeNode traversal(int[] nums, int left, int right) {
        if (left >= right) return null;
        int index = right - 1;
        int maxIndex = left;
        while (index > left) {
            if (nums[maxIndex] < nums[index]) maxIndex = index;
            index--;
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = traversal(nums, left, maxIndex);
        root.right = traversal(nums, maxIndex + 1, right);
        return root;
    }

    private static TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums, 0, nums.length);
    }
}
